import java.util.*;

/**
 * @author LKQ
 * @date 2022/2/22 11:27
 * @description
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] words = {"i", "love", "leetcode", "i", "love", "coding"};
        solution.topKFrequent(words, 2);
    }
    public List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        // 统计每个单词出现的频率
        Map<String, Integer> map = new HashMap<>();
        for (String word: words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        // 桶排序
        List<String>[] list = new List[words.length + 1];
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            String word = entry.getKey();
            int cnt = entry.getValue();
            if (list[cnt] == null) {
                list[cnt] = new ArrayList<>();
            }
            list[cnt].add(word);
        }
        for (int i = list.length -1;  i >= 0 && ret.size() < k; i--) {
            if (list[i] == null) {
                continue;
            }else {
                list[i].sort(new Comparator<String>() {
                    @Override
                    public int compare(String o1, String o2) {
                        return o1.compareTo(o2);
                    }
                });
            }
            for (int j = 0; j < list[i].size() && ret.size() < k; j++) {
                ret.add(list[i].get(j));
            }
        }
        return ret;
    }
}
